package com.lee.algorithm.linkedlist;

import com.lee.algorithm.linkedlist.struct.OneWayNode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/***
 * @description: 单向链表反转
 * @author : 青石路
 * @date: 2021/11/18 18:47
 */
public class ReversalList {

    public static void main(String[] args) {
        OneWayNode node = new OneWayNode(1);
        OneWayNode node2 = new OneWayNode(2);
        OneWayNode node3 = new OneWayNode(3);
        OneWayNode node4 = new OneWayNode(4);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        List list = new LinkedList<>();
        Collections.reverse(list);

        print(node);
        System.out.println();
        node = recurReverse(null, node);
        print(node);
    }

    /**
     * 迭代处理
     * @author 博客园 @ 青石路
     * @param node
     * @return
     */
    public static OneWayNode iterateReverse(OneWayNode node) {
        OneWayNode prev = null, cur = node;
        while (cur != null) {
            node = cur.next;    // 保存下一个节点（旧链表的head）
            cur.next = prev;    // 反转，当前节点的next指向新的链表的head，cur 成为新链表的 head
            prev = cur;         // prev 赋值成 cur，回到新链表的 head
            cur = node;         // cur 处理完成之后，继续回到旧链表的 head 节点
        }
        return prev;
    }

    /**
     * 递归处理
     * @author 博客园 @ 青石路
     * @param prev 当前节点的前节点
     * @param cur 当前节点
     * @return
     */
    public static OneWayNode recurReverse(OneWayNode prev, OneWayNode cur) {
        if (cur == null) {
            return prev;
        }
        OneWayNode temp = cur.next; // 先保存下一个节点，保证链表可以遍历完
        cur.next = prev;            // 反转当前节点的next
        return recurReverse(cur, temp);
    }

    public static void print(OneWayNode node) {
        if (node == null) {
            return;
        }
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
    }
}
